package 栈;

import java.util.*;

public class No1190反转每对括号间的子串 {

    /**
     * 给出一个字符串 s（仅含有小写英文字母和括号）。
     * 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
     * 注意，您的结果中 不应 包含任何括号。
     *
     * 示例 1：
     * 输入：s = "(abcd)"
     * 输出："dcba"
     * 示例 2：
     * 输入：s = "(u(love)i)"
     * 输出："iloveu"
     * 示例 3：
     * 输入：s = "(ed(et(oc))el)"
     * 输出："leetcode"
     */

    public String reverseParentheses(String s) {

        if(s==null||s.length()==0)
            return s;

        /**
         * 以括号为基准,一个')'的就出栈存一次,然后再全部放入,继续遍历
         */

        char[] arr = s.toCharArray();
        int index=0;
        Deque<Character> stack=new ArrayDeque<>();

        while (index!=arr.length){

            char c=arr[index++];
            if(c!=')'){
                //非')'直接存入
                stack.addLast(c);
            }else{
                List<Character> list=new ArrayList<>();
                Character poll = stack.removeLast();
                while (poll!='('){
                    list.add(poll);
                    poll=stack.removeLast();
                }
                stack.addAll(list);
            }

        }

        StringBuilder stringBuilder=new StringBuilder();
        while (!stack.isEmpty()){
            stringBuilder.append(stack.removeFirst());
        }

        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        No1190反转每对括号间的子串 n=new No1190反转每对括号间的子串();
        String s = n.reverseParentheses("(u(love)i)");
        //u evol i
        //i love u
        System.out.println(s);
    }

}
